/* Try to implement a double direction link list.
 * 
 * by Stone at 2020-3-30
 */

/* LinkList ADT
 * Operations:
 *      // init and destory
 *      create_list()
 *      init();
 *      destory();
 *      
 *      // CRUD
 *      push();
 *      insert();
 *      pop();
 *      remove();
 *      get_elem();
 *      set_elem();
 *      loc_elem();
 *      has_elem();
 *
 *      // information
 *      list_length();
 *      is_empty();
 *      is_full();
 *      is_init();
 *      
 * Philosophy:
 *      * 除了creat_list()之外所有函数的返回类型均为Status,用以表示操作是否成功.
 */
#include <stdio.h>
#include <stdlib.h>

#include "LinkList.h"


#define SEG "\n===============================\n"


/* ====== ====== ======
 * functions to do some check
 * ====== ====== ======
 */

/* Check the pos to ls is valid. 
 * Param after_end: If it is false, only those pos where there is element
 * are valid, i.e. 0 <= pos < ls.length, which is supposed to be used 
 * in pop() or remove(). If it is true, one more place after the end is 
 * also valid, i.e. 0 <= pos <= ls.length,which you might expect in 
 * insert(). */
bool check_pos(LinkList *ls, ListIdx pos, bool after_end){
    if (after_end){
        if (pos >= 0 && pos <= ls->length){
            return true;
        }
    }
    else{
        if (pos >= 0 && pos < ls->length){
            return true;
        }
    }

    printf("check_pos: invalid pos\n");
    return false;
}


/* Check if the list is initialized.
 * After declaration and initialization, the address of next's prev of ls.head 
 * should be the same to the address ls.head itself, so we could know whether 
 * it is properly initialized. If the following oprations on list are also
 * properly, this test should be also available. Though it might look not so
 * beautiful.
 */
bool check_init(LinkList *ls){
    if (ls->head.next->prev == &ls->head){
        return true;
    }
    else{
        printf("check_init: list uninitialized\n");

        return false;
    }
}


/* Check if the list ls could add one node. */
bool check_max_length(LinkList *ls){
    if (ls->length +1 > ls->max_length){
        return false;
    }
    else{
        return true;
    }
}


/* Description:
 *      Such operation that concatenate two node is very common, 
 *      so it's necessary to capsule it into a function for resue. */
void concat_nodes(Node *prior, Node *rear){
    prior->next = rear;
    rear->prev = prior;
}


/* Description:
 *      Itering a linked list to get the address of node at position pos 
 *      is a common operation, so capsule it here for resue.
 * 
 * Prerequsite:
 *      The pos has already been verified that it's valid.
 * 
 * Attention: 
 *      The node at position 0 is not ls->head, but ls->head->next.*/
Node *_node_addr(LinkList *ls, ListIdx pos){
    Node *pt = &ls->head;  // head is node at position -1
    for (ListIdx i=0; i<=pos; i++){
        pt = pt->next;  // address of node at position i
    }

    return pt;
}


/* Description:
 *      A helper function that to check whether two elements are "equal". */
bool is_elem_equal(const Elem *ea, const Elem *eb){
    if (*ea == *eb){
        return true;
    }
    else {
        return false;
    }
}


/* Description:
 *      结构体定义内不能设定变量的初始值,而在用户代码中赋初值,多少有点破坏封装.
 *      因此构造了create_list()函数,在局部作用域中创建一个链表,并隐式
 *      地调用initList()初始化,然后将这个局部的链表后通过值传递赋给外部的链表.
 *      于是就可以用
 *          LinkList ls = create_list();
 *      这样的代码来赋初值了.由于开始时数据结构需要的资源非常小,因此这样的
 *      值传递对性能影响不大.
 *
 *      2020-4-2更新：
 *      对于一个数据结构，可能C-Style的用法都是先init，然后destory吧。而这个
 *      函数原先是用Python的习惯来思考的，可能不是很C-Style，现在发现应该把
 *      初始值的设置放在init函数里，而这个函数就不是很必要了，因此就当成一个
 *      可以把声明和初始化写在一行的辅助函数来用吧。
 */
struct LinkList create_list(){
    struct LinkList ls;

    initList(&ls, MAX_LEN);
    return ls;
}


/* Prerequisite:
 *      The parameter ls is created, and allocated memory.
 *
 * Result:
 *      The LinkList is set to apporiate value.
 */
Status initList(LinkList *ls, int max_length){
    // TODO check if the list is already initialized.
    
    if (max_length > MAX_LEN){
        printf("init: the length is too long, max length allowed is %i\n", MAX_LEN);
    
        return ERR;
    }

    ls->head.prev = NULL;
    ls->head.next = &ls->tail;
    ls->tail.prev = &ls->head;
    ls->tail.next = NULL;

    ls->head.data = (Elem)ELEM_NULL;
    ls->tail.data = (Elem)ELEM_NULL;
    ls->length = 0;
    ls->max_length = max_length;

    return OK;
}


/* Prerequisite:
 *      The list ls is initialized.
 *
 * Result:
 *      Free the memory of all the nodes, except head and tail. Then set the
 *      list to inintial state. 
 */
Status destroyList(LinkList *ls){
    
    Node *cur = ls->head.next;
    Node *cur_to_del;
    for (ListIdx i=0; i < ls->length; i++){
        cur_to_del = cur;
        cur = cur->next;
        free(cur_to_del);
    }

    initList(ls, ls->max_length);

    return OK;
}


/* Prerequisite:
 *      * The list ls is initialized.
 *      * The position to insert satdisfy 0 <= i < ls.length
 */
Status insert(LinkList *ls, ListIdx pos, Elem e){
    if (!check_max_length(ls)){
        printf("insert: reach max_length.\n");
        return ERR;
    }
    else if (!check_pos(ls, pos, true)){
        return ERR;
    }
    
    // Create node to store new element
    Node *new_node = malloc(sizeof(Node));
    new_node->data = e;
    
    // Rearrange list
    Node *cur = _node_addr(ls, pos);
    concat_nodes(cur->prev, new_node);
    concat_nodes(new_node, cur);
    
    // Update list info
    ls->length += 1;    
    
    return OK;
}


/* Prerequsite:
 *      1. The list is initialized.
 *      2. Position to remove satisfied: 0 <= pos < ls->length;*/
Status _remove(LinkList *ls, ListIdx pos){
    if(!check_pos(ls, pos, false)){
        return ERR;
    }

    // do the remove
    Node *node_to_remove = _node_addr(ls, pos);
    concat_nodes(node_to_remove->prev, node_to_remove->next);
    free(node_to_remove);

    // update list info
    ls->length -= 1;

    return OK;
}


/* Prerequsite for get_elem() and set_elem():
 *      1. List is not empty and initialized.
 *      2. 0 <= pos <= ls->length - 1 */
Status get_elem(LinkList *ls, ListIdx pos, Elem *rslt){
    if (!check_pos(ls, pos, false)){
        return ERR;
    }
    
    Node *n = _node_addr(ls, pos);
    *rslt = n->data;

    return OK;
}


Status set_elem(LinkList *ls, ListIdx pos, Elem new_data){
    if (!check_pos(ls, pos, false)){
        return ERR;
    }

    Node *n = _node_addr(ls, pos);
    n->data = new_data;

    return OK;
}


/* Prerequsite:
 *      1. The list has been initialized.
 *
 * Description:
 *      To search the whole list to find if there is an element equals to e.
 *      If it does, returen the node's address and Status OK, otherwise,
 *      return address NULL and Status ERR. */
Status loc_elem(LinkList *ls, Elem e, Node **rslt){
    
    Node * const fail_addr = NULL;
    // Actually to verify if length == 0 is enough, but to verify condition that 
    // length < 0 by the way might be a good idea(I don't know) in case of some
    // accident happening.
    if (ls->length <= 0){
        *rslt = fail_addr;
        return ERR;
    }

    //searching...
    for (int i=0; i < ls->length; i++){
        Node *n = _node_addr(ls, i);
        if (is_elem_equal(&e, &n->data)){
            *rslt = n;
            return OK;
        }
    }

    //element no found
    *rslt = fail_addr;
    return ERR;
}


/* Prerequsite:
 *      1. The list is initialized.
 *
 * Description:
 *      To see if the list ls has the same element e.*/
bool has_elem(LinkList *ls, Elem e){
    Node *not_used;

    if (OK == loc_elem(ls, e, &not_used)){
        return true;
    }
    else{
        return false;
    }
}


/* ===== ===== =====
 *  Some functions to get the list's information.
 * ===== ===== =====
 */
bool is_init(LinkList *ls){
    const Elem elem_null = (Elem)ELEM_NULL;  // for temporary use

    if (    ls->head.prev == NULL \
            && ls->tail.next == NULL \
            && is_elem_equal(&ls->head.data, &elem_null) \
            && is_elem_equal(&ls->tail.data, &elem_null)
       )
    {
        return true;
    }

    return false;
}

bool is_empty(LinkList *ls){
    if (is_init(ls) && ls->length == 0){
        return true;
    }
    return false;
}


bool is_full(LinkList *ls){
    if (is_init(ls) && ls->length == ls->max_length){
        return true;
    }
    return false;
}


ListIdx list_length(LinkList *ls){
    if (!is_init(ls)){
        printf("list_length(): list not initialized\n");  // nothing more could be done except some prompting.
    }
    return ls->length;
}


void test_check(){
    printf(SEG);

    int num = 5;

    printf("test_check():\n");

    printf("check_init...\n");
    LinkList ls;
    printf("before init: %i\n", check_init(&ls));

    initList(&ls, num);
    printf("after init: %i\n", check_init(&ls));

    printf("\ncheck_pos...\n");
    int pos=0;
    printf("after = false\n");
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, false));
   
    ls.length = num;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, false));

    pos = ls.length;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, false));
    
    pos = ls.length-1;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, false));
    
    printf("\nafter = true\n");
    ls.length=0;
    pos = 0;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, true));

    ls.length = num;
    pos = ls.length;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, true));

    pos = ls.length -1;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, true));

    pos = ls.length;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, true));

    pos = ls.length +1;
    printf("len: %i, pos: %i, check: %i\n", ls.length, pos, check_pos(&ls, pos, true));
}


void test_init_destory(){
    LinkList ls;
    initList(&ls, MAX_LEN);

    destroyList(&ls);
}


void test_insert_remove(){
    printf(SEG);
    printf("test_insert_remove():\n");

    int num = 5, pos=0;
    Elem test_e = 66;

    LinkList lls;
    LinkList *ls = &lls;  // for convenience
    initList(ls, num);
    
    // test insert
    printf("test insert()...\n");
    pos = -1;
    insert(ls, pos, test_e);
    printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);

    pos = num + 1;
    insert(ls, pos, test_e);
    printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);

    
    pos = 0;
    for (int i=0; i<num; i++){
        insert(ls, pos, i);
        printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);
    }

    printf("insert one more.\n");
    pos = 0;
    insert(ls, pos, test_e);
    printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);

    
    // test remove
    printf("\ntest remove()...\n");
    
    pos = -1;
    _remove(ls, pos);
    printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);

    pos = num + 1;
    _remove(ls, pos);
    printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);

    for (int i=0; i<num; i++){
        pos = 0;
        _remove(ls, pos);
        printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);
    }
    
    pos = 0;
    _remove(ls, pos);
    printf("pos: %i, length: %i, max_length: %i\n", pos, ls->length, ls->max_length);




    destroyList(ls);
}


void test_node_addr(){
    LinkList ls;
    
    int num = 5;
    initList(&ls, num);
    
    // Create nodes
    Node *cur_temp = &ls.head;
    for (int i=0; i<num; i++){
        cur_temp->next = malloc(sizeof(Node));
        cur_temp = cur_temp->next;
    }
    
    // begin to test
    printf("\n%saddr of nodes:\n", SEG);
    cur_temp = &ls.head;
    for (int i=0; i<num; i++){
        cur_temp = cur_temp->next;
        printf("idx: %i, addr:%p  %p\n", i, cur_temp, _node_addr(&ls, i));
    }
}


void test_get_set_loc_has(){
    printf(SEG);

    int num = 5, pos=0;
    Elem rslt;

    // create list
    LinkList _ls;
    LinkList *ls = &_ls;  // for convenience
    initList(ls, num);

    for (int i=0; i<num; i++){
        insert(ls, i, i);
    }


    // test get_elem()
    printf("test get_elem()...\n");
    for (int i=0; i<num; i++){
        pos = i;
        get_elem(ls, pos, &rslt);
        printf("pos: %i, elem: %i\n", pos, rslt);
    }

    pos = -1;
    get_elem(ls, pos, &rslt);
    printf("pos: %i, elem: %i\n", pos, rslt);

    pos = num;
    get_elem(ls, pos, &rslt);
    printf("pos: %i, elem: %i\n", pos, rslt);
    

    //test set_elem()
    printf("\ntest set_elem()...\n");
    for (int i=0; i<num; i++){
        pos = i;
        Node *n = _node_addr(ls, pos);
        set_elem(ls, pos, n->data +10);

        printf("pos: %i, elem: %i\n", pos, n->data);
    }
    
    pos = -1;
    set_elem(ls, pos, 100);
    printf("pos: %i\n", pos);

    pos = num;
    set_elem(ls, pos, 100);
    printf("pos: %i\n", pos);


    //test loc_elem()
    printf("\ntest loc_elem()...\n");
    Status rlst_status;
    Node *n_rlst, *n_target = ls->head.next;
    Elem elem_to_loc = n_target->data;

    rlst_status = loc_elem(ls, elem_to_loc, &n_rlst);
    printf("target_addr:%p\n", n_target);
    printf("result_addr:%p, Status: %i, elem:%i\n", n_rlst, rlst_status, elem_to_loc);
    
    n_target = n_target->next;
    elem_to_loc = n_target->data;
    rlst_status = loc_elem(ls, elem_to_loc, &n_rlst);
    printf("target_addr:%p\n", n_target);
    printf("result_addr:%p, Status: %i, elem:%i\n", n_rlst, rlst_status, elem_to_loc);
    

    //test has_elem()
    printf("\ntest has_elem()...\n");
    Elem elem_test = 2333;
    printf("elem_test: %i, result: %i\n", elem_test, has_elem(ls, elem_test));
    
    elem_test = ls->head.next->data;
    printf("elem_test: %i, result: %i\n", elem_test, has_elem(ls, elem_test));

    elem_test = ls->head.next->next->data;
    printf("elem_test: %i, result: %i\n", elem_test, has_elem(ls, elem_test));

    destroyList(ls);
}


void test_information_functions(){
    void print_list(LinkList *ls){
        printf("head.prev: %p, tail.next:%p, length:%i, max_length:%i\n",
            ls->head.prev, ls->tail.next, ls->length, ls->max_length);
        printf("is_init(): %i\n", is_init(ls));
        printf("list_length(): %i\n", list_length(ls));
        printf("is_empty(): %i\n", is_empty(ls));
        printf("is_full(): %i\n", is_full(ls));
    }

    printf(SEG);
    printf("test_information_functions()\n");
    int num = 6;


    LinkList lls;
    LinkList *ls = &lls;
    printf("list created\n");
    print_list(ls);

    initList(ls, num);
    printf("\nlist initialized.\n");
    print_list(ls);

    printf("\ninserting some elements(1 element less than max_length)...\n");
    for (int i=0; i < num-1; i++){
        insert(ls, 0, i);
    }
    print_list(ls);

    printf("\ninsert one more");
    insert(ls, 0, 0);
    print_list(ls);
    


    destroyList(ls);

}


int main(){
    
    //LinkList ls = create_list();

    test_check();
    test_init_destory();
    test_node_addr();
    test_insert_remove();
    
    test_get_set_loc_has();
    test_information_functions();

    return 0;
}









